package de.fuberlin.inf.alp3.ue10;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Set;
import java.util.Map;

public class Node {
    private final Set<Node> requires = new HashSet<Node>();
    private int weight;
    public String name;
    
    private static final Map<Node, StackItem> stack = 
        new LinkedHashMap<Node, StackItem>(); 
    
    @Override
    public String toString() { return name+"("+weight+")"; }

    public Node (String name, int w) { this.weight = w; this.name = name; }
    
    public void add(Node n) { this.requires.add(n); }
    
    public void getCriticalPath() {
        depthFirstSearchReverse(); // topologically sorted
        Iterator<Map.Entry<Node,StackItem>> i = Node.stack.entrySet().iterator();
        Map.Entry<Node, StackItem> current = i.next();
        current.getValue().weight = current.getKey().weight; // starting node
        while (i.hasNext()) {
            current = i.next();
            for (Node n : current.getKey().requires) {
                int w = current.getKey().weight + Node.stack.get(n).weight;
                if ((w > current.getValue().weight) ||
                        (current.getValue().forerunner == null)) {
                    current.getValue().weight = w;
                    current.getValue().forerunner = n;
                }
            }
        }
        System.out.println("Kosten: " + current.getValue().weight);
        System.out.println(printPath());
    }
    
    private String printPath() {
        if (Node.stack.get(this).forerunner == null) return this.toString();
        return Node.stack.get(this).forerunner.printPath() + ", " + this;
    }

    private void depthFirstSearchReverse() {
        if (Node.stack.containsKey(this)) return;
        for (Node n : this.requires) n.depthFirstSearchReverse();
        Node.stack.put(this, new StackItem(this.weight, null));
    }

    private class StackItem {
        int weight;
        Node forerunner;
        public StackItem(int weight, Node forerunner) {
            this.weight = weight; this.forerunner = forerunner;
        }
        @Override
        public String toString() { return "W: " + weight + ", F: "+forerunner; }
    }
}